#include "CostumUtils.h"
#include <vector>

using std::vector;

IndexAndMax findMaxCrossingSubarray(int * list, int low, int mid, int high);

IndexAndMax findMaxSubarray(int * list, int low, int high)
{
	if (low == high) {
		IndexAndMax *re = new IndexAndMax(low, high, list[low]);
		return *re;
	} else {
		int mid = (low + high) / 2;

		IndexAndMax left = findMaxSubarray(list, low, mid);
		IndexAndMax right = findMaxSubarray(list, mid + 1, high);
		IndexAndMax crossing = findMaxCrossingSubarray(list, low, mid, high);

		if (left.maxSum >= right.maxSum && left.maxSum >= crossing.maxSum) {
			return left;
		} else if (right.maxSum >= left.maxSum && right.maxSum >= crossing.maxSum) {
			return right;
		} else {
			return crossing;
		}
	}
}

int findMaxSubarray(int *list, int length)
{
	int curSum = 0, maxSum = 0;
	for (int i = 0; i < length; i++) {
		curSum += list[i];
		if (curSum > maxSum) {
			maxSum = curSum;
		} else if (curSum < 0) {
			curSum = 0;
		}
	}
	return maxSum;
}

IndexAndMax findMaxCrossingSubarray(int * list, int low, int mid, int high)
{
	//left side
	int leftIndex = 0;
	int leftSum = -INFTY;
	int sum = 0;
	int lMid = mid;
	while (lMid >= low) {
		sum += list[lMid];
		if (sum > leftSum) {
			leftSum = sum;
			leftIndex = lMid;
		}
		lMid--;
	}

	//right side
	int rightIndex = 0;
	int rightSum = -INFTY;
	sum = 0;
	int rMid = mid + 1;
	while (rMid <= high) {
		sum += list[rMid];
		if (sum > rightSum) {
			rightSum = sum;
			rightIndex = rMid;
		}
		rMid++;
	}
	IndexAndMax *re = new IndexAndMax(leftIndex, rightIndex, leftSum + rightSum);
	return *re;
}